package LeetCode;

import java.util.LinkedList;
import java.util.Queue;

public class No230 {
    public int kthSmallest(TreeNode root, int k) {
        if(root.left!=null) return kthSmallest(root.left,k);
        k--;
        if(k==0) return root.val;
        if(root.right!=null) return kthSmallest(root.right,k);



        Queue<TreeNode> queue = new LinkedList<>();
        visitNode(root,queue);
        while(k>1){
            queue.poll();
            k--;
        }
        return queue.poll().val;
    }

    public void visitNode(TreeNode node, Queue<TreeNode> queue){
        if(node==null) return;
        if(node.left!=null) visitNode(node.left,queue);
        queue.add(node);
        if(node.right!=null) visitNode(node.right,queue);
    }
}
